package com.cskaoyan.day03.queue;

/**
 * @author stone
 * @date 2022/01/29 16:25
 */
public class ArrayQueue<T> {
    Object[] elements;
    int size;
    private static final int INIT_CAPACITY = 10;
    private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;
    private int head;
    private int rear; //如果放入数据的话，rear就是对应的下标

    public ArrayQueue() {
        elements = new Object[INIT_CAPACITY];
    }

    public ArrayQueue(int capacity) {
        if (capacity < 1 || capacity > MAX_CAPACITY) {
            throw new RuntimeException("参数不合法");
        }
        elements = new Object[capacity];
    }

    //offer方法有可能导致扩容
    public boolean offer(T value) {
        if (elements.length == size) {
            //扩容
            int newLength = getLength();
            grow(newLength);
        }
        //放入到rear位置，rear后移
        elements[rear] = value;
        //rear++;
        rear = (rear + 1) % elements.length;
        size++;
        return true;
    }

    private void grow(int newLength) {
        Object[] newElements = new Object[newLength];
        for (int i = 0; i < elements.length; i++) {
            newElements[i] = elements[(head + i) % elements.length]; //head+i有可能超过elements.length → 超过会导致下标越界
        }
        elements = newElements;
        head = 0;
        rear = size;
    }

    private int getLength() {
        int oldLength = elements.length;
        int newLength = oldLength << 1;
        if (newLength < 0 || newLength > MAX_CAPACITY) {
            newLength = MAX_CAPACITY;
        }
        if (oldLength == newLength) {
            throw new RuntimeException("队列满了");
        }
        return newLength;
    }

    public T poll() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        //如果不为空
        T value = (T) elements[head];
        if (size == 1) {//如果队列中只有一条，poll之后，head和rear会相遇 → head和rear置零
            head = 0;
            rear = 0;
        }else {
            //从head出，head后移
            head = (head + 1) % elements.length;

        }
        size--;

        return value;
    }
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return (T) elements[head];
    }


    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}
